//
//  ProblemOffer11.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/10.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 11. 旋转数组的最小数字
 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

 示例 1：
     输入：[3,4,5,1,2]
     输出：1
 示例 2：
     输入：[5,6,0,1,2,3,4]
     输出：0
 */
@objcMembers class ProblemOffer11: NSObject {
    func solution() {
        print(minArray([3,4,5,1,2]))
        print(minArray([2,2,2,0,1]))
        print(minArray([5,6,0,1,2,3,4]))
        print(minArray([5,1,2,3,4]))
        print(minArray([1,3,5]))
        print(minArray([3,1,1]))
        print(minArray([5,5,1]))
        print(minArray([3,1,1,1,1,1]))
        print(minArray([5,5,6,6,7,7,1]))
        print(minArray([3,3,1,3]))
    }
    
    func minArray(_ numbers: [Int]) -> Int {
        var l = 0
        var r = numbers.count - 1
        var mid = 0
        while l < r {
            mid = l + (r - l) >> 1
            if numbers[mid] < numbers[r] {
                r = mid
            } else if numbers[mid] > numbers[r] {
                l = mid + 1
            } else {
                r -= 1
            }
        }
        return numbers[l]
    }
}
